# 给定一个表达式如 expression = "e + 8 - a + 5" 和一个求值映射，如 {"e": 1}（给定的形式为 evalvars = [
# "e"] 和 evalints = [1]），返回表示简化表达式的标记列表，例如 ["-1*a","14"] 
# 
#  
#  表达式交替使用块和符号，每个块和符号之间有一个空格。 
#  块要么是括号中的表达式，要么是变量，要么是非负整数。 
#  变量是一个由小写字母组成的字符串（不包括数字）。请注意，变量可以是多个字母，并注意变量从不具有像 "2x" 或 "-x" 这样的前导系数或一元运算符 。 
# 
#  
# 
#  表达式按通常顺序进行求值：先是括号，然后求乘法，再计算加法和减法。 
# 
#  
#  例如，expression = "1 + 2 * 3" 的答案是 ["7"]。 
#  
# 
#  输出格式如下： 
# 
#  
#  对于系数非零的每个自变量项，我们按字典排序的顺序将自变量写在一个项中。 
#  
#  例如，我们永远不会写像 “b*a*c” 这样的项，只写 “a*b*c”。 
#  
#  项的次数等于被乘的自变量的数目，并计算重复项。我们先写出答案的最大次数项，用字典顺序打破关系，此时忽略词的前导系数。 
#  
#  例如，"a*a*b*c" 的次数为 4。 
#  
#  项的前导系数直接放在左边，用星号将它与变量分隔开(如果存在的话)。前导系数 1 仍然要打印出来。 
#  格式良好的一个示例答案是 ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"] 。 
#  系数为 0 的项（包括常数项）不包括在内。 
#  
#  例如，“0” 的表达式输出为 [] 。 
#  
#  
# 
#  注意：你可以假设给定的表达式均有效。所有中间结果都在区间 [-2³¹, 2³¹ - 1] 内。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]
# 输出：["-1*a","14"]
#  
# 
#  示例 2： 
# 
#  
# 输入：expression = "e - 8 + temperature - pressure",
# evalvars = ["e", "temperature"], evalints = [1, 12]
# 输出：["-1*pressure","5"]
#  
# 
#  示例 3： 
# 
#  
# 输入：expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
# 输出：["1*e*e","-64"]
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= expression.length <= 250 
#  expression 由小写英文字母，数字 '+', '-', '*', '(', ')', ' ' 组成 
#  expression 不包含任何前空格或后空格 
#  expression 中的所有符号都用一个空格隔开 
#  0 <= evalvars.length <= 100 
#  1 <= evalvars[i].length <= 20 
#  evalvars[i] 由小写英文字母组成 
#  evalints.length == evalvars.length 
#  -100 <= evalints[i] <= 100 
#  
# 
#  Related Topics 栈 递归 哈希表 数学 字符串 👍 63 👎 0
import collections
import re
from collections import defaultdict
from typing import List


class Poly(collections.Counter):
    """
    Poly本质上是一个字典，因为它继承了collections.Counter
    多项式是 3*a*b + 2*a - 5，那么 self 可能看起来像这样：
    {
    ("a", "b"): 3,  # 表示 3*a*b
    ("a",): 2,      # 表示 2*a
    (): -5          # 表示常数项 -5
    }
    __add__, __sub__, __mul__这些方法是 Python 中的特殊方法 （也叫魔术方法），它们的作用是让类支持特定的操作符：

    __add__：支持 + 操作符。
    __sub__：支持 - 操作符。
    __mul__：支持 * 操作符。
    例如，当我们写 left + right 时，Python 实际上会调用 left.__add__(right)
    需注意，题目中已给出没有除号
    """

    def __add__(self, other):
        """
        update() 是 collections.Counter 提供的一个方法，用来更新字典的内容。
        它的作用是：把 other 中的每一项加到 self 中。
        如果 self 中已经有某个键（比如 ("a",)），就直接加上对应的值；如果没有这个键，就新增一个键，并赋上 other 中的值。
        实现效果 self = 2a+2b other = 2c+2a 返回self = 4a + 2b + 2c
        """
        self.update(other)
        return self

    def __sub__(self, other):
        # 和加法同理，就是加上负值
        self.update({k: -v for k, v in other.items()})
        return self

    def __mul__(self, other):
        ans = Poly()
        # 两个for循环实现交替相乘。例如把（a+b）*（a-b）变为a*a + a*b + b*a + -b*b
        for k1, v1 in self.items():
            for k2, v2 in other.items():
                """
                k1+k2不会合并也不会去重，
                比如("a", "b"): 3,  # 表示 3*a*b
                ("a",): 2,      # 表示 2*a
                那么k1+k2 = (a,a,b)目的是为了得到所有要相乘的未知数。对于系数v1 v2 直接相乘就可以了
                """
                ans.update({tuple(sorted(k1 + k2)): v1 * v2})
        return ans

    def evaluate(self, evalmap):
        """
        将evalvars = ["xx"], evalints = [xx]给出的具体值带入self
        :param evalmap:
        :return:
        """
        ans = Poly()
        for k, c in self.items():
            free = []
            for token in k:
                if token in evalmap:
                    c *= evalmap[token]
                else:
                    # 没有被替换的变量将会被添加到free中，最后会用free重新组成字典，也就是相当于把已知变量替换掉了
                    free.append(token)
            ans[tuple(free)] += c
        return ans

    def to_list(self):
        """
        这个方法地作用时将结果从字典转化为固定地输出格式，类似["1*e*e","-64"]的
        sorted(self.items(),key=lambda x: (-len(x[0]), x[0])：意思是先按照字符数降序，再按照字典序升序
        if v : 为了去除无意义的系数0
        "*".join((str(v),) + k)：(str(v),)的意思是把str(v)转化为只有一个元素的元组，然后加上k形成一个新元组。在这个新元组中，每个元素用*连接
        :return:
        """
        return ["*".join((str(v),) + k)
                for k, v in sorted(self.items(),
                                   key=lambda x: (-len(x[0]), x[0]))
                if v]


class Solution(object):
    def basicCalculatorIV(self, expression, evalvars, evalints):
        evalmap = dict(zip(evalvars, evalints))

        def combine(left, right, symbol):
            if symbol == '+': return left + right
            if symbol == '-': return left - right
            if symbol == '*': return left * right
            raise

        # 将提取的数字或字母转化为字典例如"8"，将其作为常数项 {(): 8}，"a"，将其作为键 {("a",): 1}
        def make(expr):
            ans = Poly()
            if expr.isdigit():
                ans.update({(): int(expr)})
            else:
                ans[(expr,)] += 1
            return ans

        def parse(expr):
            # 存储数字或字母
            bucket = []
            # 存储符号
            symbols = []
            i = 0
            while i < len(expr):
                if expr[i] == '(':
                    bal = 0
                    for j in range(i, len(expr)):
                        if expr[j] == '(': bal += 1
                        if expr[j] == ')': bal -= 1
                        # 匹配到当前的左括号对应的右括号时，可以break
                        if bal == 0: break
                    # 递归得出括号内的内容
                    bucket.append(parse(expr[i + 1:j]))
                    i = j
                # 检查是否时字母或数字
                elif expr[i].isalnum():
                    for j in range(i, len(expr)):
                        if expr[j] == ' ':
                            bucket.append(make(expr[i:j]))
                            break
                    else:
                        bucket.append(make(expr[i:]))
                    i = j
                elif expr[i] in '+-*':
                    symbols.append(expr[i])
                i += 1
            # 处理乘除
            for i in range(len(symbols) - 1, -1, -1):
                if symbols[i] == '*':
                    # 若是* 就把对应的两个数相乘
                    bucket[i] = combine(bucket[i], bucket.pop(i + 1),
                                        symbols.pop(i))
            # 处理加减
            if not bucket: return Poly()
            ans = bucket[0]
            # enumerate(symbols, 1)意思是索引从1开始，这样可以直接对应到 bucket[i]
            for i, symbol in enumerate(symbols, 1):
                ans = combine(ans, bucket[i], symbol)

            return ans

        P = parse(expression).evaluate(evalmap)
        return P.to_list()


# 测试
print(Solution().basicCalculatorIV(expression="(e + 8) * (a - 8)", evalvars=["a"], evalints=[10]
                                   ))
